package com.yubest;

/**
 * @Author hweiyu
 * @Description
 * @Date 2022/1/5 9:23
 */
public class Kmp {

    public static void main(String[] args) {
        System.out.println(new Kmp().match("abcdababcdabddabcdabd", "abcdabd"));
    }

    public int match(String m, String p) {
        //预处理，生成next数组
        int[] next = getNext(p);
        for (int i = 0, j = 0; i < m.length(); i++) {
            while (j > 0 && m.charAt(i) != p.charAt(j)) {
                //遇到坏字符时，查询next数组并改变模式串的起点
                j = next[j - 1];
            }
            if (m.charAt(i) == p.charAt(j)) {
                j++;
            }
            if (j == p.length()) {
                //匹配成功，返回下标
                return i - p.length() + 1;
            }
        }
        return -1;
    }

    private int[] getNext(String p) {
        int[] next = new int[p.length()];
        for (int i = 1, j = 0; i < p.length(); i++) {
            while (j > 0 && p.charAt(i) != p.charAt(j)) {
                //回溯
                j = next[j - 1];
            }
            if (p.charAt(i) == p.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
